package tools.gis.antennaReader;

/*
 * Implements the k-means algorithm
 *
 * Manas Somaiya
 * Computer and Information Science and Engineering
 * University of Florida
 *
 * Created: October 29, 2003
 * Last updated: October 30, 2003
 *
 */

import java.io.*;
import java.util.*;

import tools.Log;

import datatypes.Antenna;



/**
 * Implements the k-means algorithm
 * 
 * Edit by kj1 voor antennes enzo
 * 
 * @author	Manas Somaiya	mhs@cise.ufl.edu
 */ 
public class KMeans {


	/** Number of clusters */
	private int k;


	/** Array of clusters */
	private cluster[] clusters;


	/** Number of iterations */
	private int nIterations;


	/** Vector of data points */
	private Vector kMeansPoints;


	/**
	 * Returns a new instance of kMeans algorithm
	 *
	 * @param	k		number of clusters
	 * @param	kMeansPoints	List containing objects of type kMeansPoint
	 */
	public KMeans(int k, List<Antenna> a ) {
		this.kMeansPoints=new Vector();
		for (int i =0; i< a.size(); i++)
			kMeansPoints.add(new kMeansPoint((int)a.get(i).getX(), (int)a.get(i).getY(), (Antenna)a.get(i)));	
		this.k = k;
		this.clusters = new cluster[this.k];
		this.nIterations = 0;

	} // end of kMeans()

	/**
	 * Returns a new instance of kMeans algorithm
	 *
	 * @param	k		number of clusters
	 * @param	kMeansPoints	List containing objects of type kMeansPoint
	 */
	public KMeans(int k, Antenna[] a ) {
		this.kMeansPoints=new Vector(kMeansPoints);
		for (int i =0; i< a.length; i++)
			kMeansPoints.add(new kMeansPoint((int)a[i].getX(), (int)a[i].getY(), a[i]));	
		this.k = k;
		this.clusters = new cluster[this.k];
		this.nIterations = 0;

	} // end of kMeans()

	/**
	 * Runs the k-means algorithm over the data set
	 */
	public Antenna[] runKMeans() {

		Log.add(this,"Clustering...");
		// Select k points as initial means
		for (int i=0; i < k; i++){

			this.clusters[i] = new cluster(i);
			this.clusters[i].setMean((kMeansPoint)(this.kMeansPoints.get((int)(Math.random() * this.kMeansPoints.size()))));

		}


		do {
			// Form k clusters
			Iterator i = this.kMeansPoints.iterator();
			while (i.hasNext())
				this.assignToCluster((kMeansPoint)(i.next()));

			this.nIterations++;

		}
		// Repeat while centroids do not change
		while (this.updateMeans());

		
		Antenna[] antennalist = new Antenna[kMeansPoints.size()];
		/*
		for (int i = 0; i < kMeansPoints.size(); i++) {
			Antenna a = (Antenna)((kMeansPoint)(this.kMeansPoints.get(i))).getObject();
			int clusternr = ((kMeansPoint)(this.kMeansPoints.get(i))).getClusterNumber();
			int loc = clusternr * k;
			while (antennalist[loc%kMeansPoints.size()] != null)
				loc++;
			antennalist[loc%kMeansPoints.size()] = a;
			
		}
		*/
		int index = 0;
		int clusternr = 0;
		while (index != kMeansPoints.size()) {
			for (int i = 0; i < kMeansPoints.size(); i++) {
				Antenna a = (Antenna)((kMeansPoint)(this.kMeansPoints.get(i))).getObject();
				int clusternrtmp = ((kMeansPoint)(this.kMeansPoints.get(i))).getClusterNumber();
				
				if (clusternrtmp == clusternr) {
					antennalist[index] = a;
					((kMeansPoint)(this.kMeansPoints.get(i))).assignToCluster(-1);
					index++;
				}
				
			}			
			clusternr++;
			
		}
		Log.add(this,"Clustering done");
		return antennalist;
	} // end of runKMeans()


	/**
	 * Assigns a data point to one of the k clusters based on its distance from the means of the clusters
	 *
	 * @param	dp	data point to be assigned
	 */
	private void assignToCluster(kMeansPoint dp) {

		int currentCluster = dp.getClusterNumber();
		double minDistance = distance(dp, this.clusters[currentCluster].getMean());;

		for (int i=0; i <this.k; i++)
			if (distance(dp, this.clusters[i].getMean()) < minDistance) {

				minDistance = distance(dp, this.clusters[i].getMean());
				currentCluster = i;

			}

		dp.assignToCluster(currentCluster);	

	} // end of assignToCluster


	/**
	 * Updates the means of all k clusters, and returns if they have changed or not
	 *
	 * @return	have the updated means of the clusters changed or not
	 */
	private boolean updateMeans() {

		boolean reply = false;

		int[] x = new int[this.k];
		int[] y = new int[this.k];
		int[] size = new int[this.k];
		kMeansPoint[] pastMeans = new kMeansPoint[this.k];

		for (int i=0; i<this.k; i++) {

			x[i] = 0;
			y[i] = 0;
			size[i] = 0;
			pastMeans[i] = this.clusters[i].getMean();

		}

		Iterator i = this.kMeansPoints.iterator();
		while (i.hasNext()) {


			kMeansPoint dp = (kMeansPoint)(i.next());
			int currentCluster = dp.getClusterNumber();

			x[currentCluster] += dp.getX();
			y[currentCluster] += dp.getY();
			size[currentCluster]++;

		}

		for (int j=0; j < this.k; j++ ) 
			if(size[j] != 0) {

				x[j] /= size[j];
				y[j] /= size[j];
				kMeansPoint temp = new kMeansPoint(x[j], y[j], null);
				temp.assignToCluster(j);
				this.clusters[j].setMean(temp);
				if (distance(pastMeans[j], this.clusters[j].getMean()) !=0 )
					reply = true;

			}

		return reply;

	} // end of updateMeans()


	/**
	 * Returns the value of k
	 *
	 * @return	the value of k
	 */
	public int getK() {

		return this.k;

	} // end of getK()


	/**
	 * Returns the specified cluster by index
	 *
	 * @param	index	index of the cluster to be returned
	 * @return	return the specified cluster by index
	 */
	public cluster getCluster(int index) {

		return this.clusters[index];

	} // end of getCluster()


	/**
	 * Returns the string output of the data points
	 *
	 * @return  the string output of the data points
	 */
	public String toString(){

		return this.kMeansPoints.toString();

	} // end of toString()


	/**
	 * Returns the data points
	 *
	 * @return  the data points
	 */
	public Vector getDataPoints() {

		return this.kMeansPoints ;

	} // end of getDataPoints()


	/**
	 * Returns the distance between two data points
	 *
	 * @param	dp1 	the first data point
	 * @param	dp2 	the second data point
	 * @return	the distance between the two data points
	 */
	public double distance(kMeansPoint dp1, kMeansPoint dp2) {

		double result = 0;
		double resultX = dp1.getX() - dp2.getX();
		double resultY = dp1.getY() - dp2.getY();
		result = Math.sqrt(resultX*resultX + resultY*resultY);
		return result;

	} // end of distance()



	/*
	 * Represents an abstraction for a cluster of data points in two dimensional space
	 *
	 * Manas Somaiya
	 * Computer and Information Science and Engineering
	 * University of Florida
	 *
	 * Created: October 29, 2003
	 * Last updated: October 30, 2003
	 *
	 */

	/*
	 * Represents an abstraction for a data point in two dimensional space
	 *
	 * Manas Somaiya
	 * Computer and Information Science and Engineering
	 * University of Florida
	 *
	 * Created: October 29, 2003
	 * Last updated: October 30, 2003
	 *
	 */



	/**
	 * Represents an abstraction for a data point in two dimensional space
	 * @author	Manas Somaiya	mhs@cise.ufl.edu
	 */ 
	public class kMeansPoint {


		/** Value in dimension x */
		private int x;


		/** Value in dimension y */
		private int y;


		/** Assigned cluster */
		private int clusterNumber;

		private Object o;
		

		/**
		 * Creates a new instance of data point
		 *
		 * @param	_x	value in dimension x
		 * @param	_y	value in dimension y
		 */
		public kMeansPoint(int _x, int _y, Object o) {

			this.x = _x;
			this.y = _y;
			this.clusterNumber=0;
			this.o = o;
		} // end of kMeansPoint()


		/**
		 * Assigns the data point to a cluster
		 *
		 * @param	_clusterNumber	the cluster to which this data point is to be assigned
		 */
		public void assignToCluster(int _clusterNumber) {

			this.clusterNumber = _clusterNumber;

		} // end of assignToCluster()


		/**
		 * Returns the cluster to which the data point belongs
		 *
		 * @return	the cluster number to which the data point belongs
		 */
		public int getClusterNumber() {

			return this.clusterNumber;

		} // end of getClusterNumber()


		/**
		 * Returns the value of data point in x dimension
		 *
		 * @return	the value in x dimension
		 */
		public int getX() {

			return this.x;

		} // end of getX()


		/**
		 * Returns the value of data point in y dimension
		 *
		 * @return	the value in y dimension
		 */
		public int getY() {

			return this.y;

		} // end of getY()


		public Object getObject(){
			return o;
		}

		/**
		 * Returns a string representation of this kMeansPoint
		 *
		 * @return	a string representation of this data point
		 */
		public String toString(){

			return "(" + this.x + "," + this.y + ")[" + this.clusterNumber + "]";

		} // end of toString()


		/**
		 * Main method -- to test the kMeansPoint class
		 *
		 * @param	args	command line arguments
		 *
		public static void main(String[] args) {

			kMeansPoint dp1 = new kMeansPoint(-3,-4);
			kMeansPoint dp2 = new kMeansPoint(0,4);
			System.out.println(kMeansPoint.distance(dp1, dp2));
			System.out.println(dp1.getX());
			System.out.println(dp2.getY());
			dp1.assignToCluster(7);
			System.out.println(dp1.getClusterNumber());
			dp1.assignToCluster(17);
			System.out.println(dp1.getClusterNumber());
			System.out.println(dp2.getClusterNumber());
			System.out.println(dp1);

		} // end of main()
		 */

	} // end of class


	/**
	 * Represents an abstraction for a cluster of data points in two dimensional space
	 * @author	Manas Somaiya	mhs@cise.ufl.edu
	 */
	class cluster {


		/** Cluster Number */
		private int clusterNumber;


		/** Mean data point of this cluster */
		private kMeansPoint mean;


		/**
		 * Returns a new instance of cluster
		 *
		 * @param	_clusterNumber	the cluster number of this cluster
		 */
		public cluster(int _clusterNumber) {

			this.clusterNumber = _clusterNumber;

		} // end of cluster()


		/**
		 * Sets the mean data point of this cluster
		 *
		 * @param	meanDataPoint	the new mean data point for this cluster
		 */
		public void setMean(kMeansPoint meanDataPoint) {

			this.mean = meanDataPoint;

		} // end of setMean()


		/**
		 * Returns the mean data point of this cluster
		 *
		 * @return	the mean data point of this cluster
		 */
		public kMeansPoint getMean() {

			return this.mean;

		} // end of getMean()


		/**
		 * Returns the cluster number of this cluster
		 *
		 * @return	the cluster number of this cluster
		 */
		public int getClusterNumber() {

			return this.clusterNumber;

		} // end of getClusterNumber()


	} // end of class




} // end of class


